﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0174_ReorderList : IAlgorithm
    {
        // 143. 重排链表

        // 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
        // L0 → L1 → … → Ln - 1 → Ln
        // 请将其重新排列后变为：
        // L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
        // 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

        // 提示：
        //  链表的长度范围为[1, 5 * 10^4]
        //  1 <= node.val <= 1000

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public void ReorderList(ListNode head)
        {
            if (head == null)
            {
                return;
            }
            ListNode mid = MiddleNode(head);
            ListNode l1 = head;
            ListNode l2 = mid.next;
            mid.next = null;
            l2 = ReverseList(l2);
            MergeList(l1, l2);
        }

        public ListNode MiddleNode(ListNode head)
        {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        public ListNode ReverseList(ListNode head)
        {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null)
            {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }

        public void MergeList(ListNode l1, ListNode l2)
        {
            ListNode l1_tmp;
            ListNode l2_tmp;
            while (l1 != null && l2 != null)
            {
                l1_tmp = l1.next;
                l2_tmp = l2.next;

                l1.next = l2;
                l1 = l1_tmp;

                l2.next = l1;
                l2 = l2_tmp;
            }
        }
    }
}
